Computational Topology

Toolbox

Thomas Reinke

Baylor University

June 11, 2025

Contents

  1. Introduction
  2. Triangulation and Searching
  3. Euler Characteristic
  4. Complexes (Chap. III)
  5. Homology (Chap. IV)
  1. Morse Functions (Chap. VI)
  2. Persistence (Chap. VII)
  3. Stability (Chap. VIII)
  4. Relevant R Packages

Introduction

  • Based on “Computational Topology: An Introduction” by Herbert Edelsbrunner and John Harer.
  • Focuses on the blend of geometry, topology, and algorithms.
  • Aims to bring these developments to a larger audience.
  • Topology provides structures, geometry gives a concrete face to topological structures, and algorithms offer a means to construct them at a level of complexity necessary for practical applications.

Triangulation and Searching

  • A triangulation of a topological space X is a simplicial complex K together with a homeomorphism between X and the underlying space of K, \(|K|\).
  • A space is triangulable if it has a triangulation.
  • Searching a Triangulation: Involves using a data structure that represents a surface’s triangulation to determine its topological properties, such as orientability or genus.
    • Example: Triangulation of a simple closed polygon involves decomposing it into triangles using its vertices and non-intersecting diagonals.
    • Example: Triangulation of a 2-manifold decomposes it into triangular regions homeomorphic to a triangle, where any two triangles meet appropriately (disjoint, shared edge, or shared vertex).

Euler Characteristic

  • A fundamental topological invariant.
  • Defined for a simplicial complex K as the alternating sum of the number of simplices in each dimension.
    • \(\chi(K) = \sum_{p \ge 0} (-1)^p n_p\), where \(n_p\) is the number of \(p\)-simplices (e.g., vertices, edges, triangles).
  • Euler-Poincaré Theorem: The Euler characteristic is also the alternating sum of its Betti numbers.
    • \(\chi(K) = \sum_{p \ge 0} (-1)^p \beta_p\).
    • \(\beta_p\) is the rank of the \(p\)-th homology group, representing the number of \(p\)-dimensional “holes”.
  • The Euler characteristic does not depend on the specific triangulation chosen for a topological space, but is an invariant of the space itself.

Complexes (Chapter III)

A decomposition of a topological space into simple pieces.

Simplicial Complexes

  • Used as the primary data structure to represent topological spaces.
  • A finite collection of simplices K such that:
    1. If \(\sigma \in K\) and \(\tau \le \sigma\) (τ is a face of σ), then \(\tau \in K\).
    2. If σ, \(\sigma_0 \in K\), then \(\sigma \cap \sigma_0\) is either empty or a face of both.
  • Simplex: The convex hull of \(k+1\) affinely independent points. A \(k\)-simplex has dimension \(k\).
    • Examples: vertex (0-simplex), edge (1-simplex), triangle (2-simplex), tetrahedron (3-simplex).
  • j-skeleton (\(K^{(j)}\)): The subcomplex consisting of all simplices of dimension \(j\) or less. The 0-skeleton is the vertex set (Vert K).
  • Star and Link:
    • The star St \(\sigma\) of a simplex \(\sigma\) in K is the set of all simplices \(\tau \in K\) that have \(\sigma\) as a face (\(\sigma \le \tau\)).
    • The closed star \(\overline{\text{St}}\sigma\) is the smallest subcomplex containing St \(\sigma\) (i.e., St \(\sigma\) and all their faces).
    • The link Lk \(\sigma\) consists of all simplices in \(\overline{\text{St}}\sigma\) that are disjoint from \(\sigma\).
    • For a vertex \(u\), \(N(u) = \bigcup_{\sigma \in \text{St } u} \text{int } \sigma\) is an open set.

Complexes (Chapter III)

Nerve

  • For a finite collection of sets \(\mathcal{F}\), the nerve Nrv \(\mathcal{F}\) is an abstract simplicial complex.
  • A subcollection \(X \subseteq \mathcal{F}\) forms a simplex in Nrv \(\mathcal{F}\) if and only if the intersection of all sets in \(X\) is non-empty (\(\bigcap X \ne \emptyset\)).
  • Nerve Theorem: Let \(\mathcal{F}\) be a finite collection of closed, convex sets in Euclidean space. Then the nerve of \(\mathcal{F}\) and the union of the sets in \(\mathcal{F}\) have the same homotopy type.
    • This also holds if \(\bigcup\mathcal{F}\) is triangulable, all sets in \(\mathcal{F}\) are closed, and all non-empty common intersections are contractible.

Delaunay Complexes

  • A geometric construction related to Voronoi diagrams.
  • Inversion / Stereographic Projection: Geometric transformations used to provide alternative views and proofs for Voronoi diagrams and Delaunay complexes, especially in relating them to convex hulls in higher dimensions.
  • Voronoi Diagram: For a finite set of points \(S \subseteq \mathbb{R}^d\), the Voronoi cell \(V_u\) of a point \(u \in S\) is the set of points \(x \in \mathbb{R}^d\) for which \(u\) is the closest point in \(S\).
    • Weighted Voronoi diagrams (power diagrams) are defined using weighted squared distance (power).
  • Delaunay Triangulation/Complex: Isomorphic to the nerve of the Voronoi diagram. A subset \(\sigma \subseteq S\) forms a simplex in the Delaunay complex iff the intersection of the Voronoi cells \(V_u\) for all \(u \in \sigma\) is non-empty. Weighted Delaunay complexes also exist.

Complexes (Chapter III)

Alpha Complexes

  • A family of subcomplexes of the Delaunay complex, parameterized by a radius \(r \ge 0\).
  • For a set of points \(S\), the Alpha complex Alpha(r) is isomorphic to the nerve of the collection of regions \(R_u(r) = B_u(r) \cap V_u\), where \(B_u(r)\) is the closed ball with center \(u\) and radius \(r\), and \(V_u\) is the Voronoi cell of \(u\).
    • Alpha complexes have canonical geometric realizations if \(S\) is in general position.
  • Čech Complexes: Defined as the nerve of a collection of balls \(B_x(r)\) for \(x \in S\). Alpha(r) \(\subseteq\) Čech(r).
  • Filtration: As the radius \(r\) increases continuously, the alpha complexes form a nested sequence (a filtration) of simplicial complexes: \(\emptyset = K_0 \subseteq K_1 \subseteq \dots \subseteq K_m = \text{Delaunay}\). This is fundamental for persistent homology.
  • Vietoris-Rips Complexes: For \(S \subseteq \mathbb{R}^d\), Vietoris-Rips(r) = {\(\sigma \subseteq S \mid \text{diam}(\sigma) \le 2r\)}. Čech(r) \(\subseteq\) Vietoris-Rips(r), and Vietoris-Rips(r) \(\subseteq\) Čech(\(\sqrt{2}r\)).

Homology (Chapter IV)

A mathematical formalism for quantitatively describing the connectivity of a space, particularly its “holes”.

Homology Groups

  • Chain Complex: A sequence of chain groups \(C_p\) and boundary homomorphisms \(\partial_p : C_p \to C_{p-1}\) such that the composition of any two consecutive boundary maps is zero (\(\partial_{p-1} \partial_p = 0\)).
  • Chains (\(C_p\)): Formal sums of p-simplices, \(c = \sum a_i \sigma_i\). Coefficients \(a_i\) are often from \(\mathbb{Z}_2\) (modulo 2), meaning \(a_i \in \{0, 1\}\). With \(\mathbb{Z}_2\) coefficients, a chain can be viewed as a set of \(p\)-simplices. The \(p\)-chains form a group \((C_p, +)\).
  • Boundary Map (\(\partial_p\)): A homomorphism \(\partial_p : C_p(K) \to C_{p-1}(K)\) that maps a \(p\)-simplex \(\sigma = [u_0, \dots, u_p]\) to the sum of its \((p-1)\)-faces: \(\partial_p \sigma = \sum_{j=0}^p [u_0, \dots, \widehat{u}_j, \dots, u_p]\).
  • Cycles (\(Z_p\)) and Boundaries (\(B_p\)):
    • A \(p\)-cycle is a \(p\)-chain \(c\) with an empty boundary (\(\partial_p c = 0\)). The group of \(p\)-cycles \(Z_p = \ker \partial_p\) is a subgroup of \(C_p\).
    • A \(p\)-boundary is a \(p\)-chain \(c\) that is the boundary of some \((p+1)\)-chain \(d\) (\(c = \partial_{p+1} d\)). The group of \(p\)-boundaries \(B_p = \text{im } \partial_{p+1}\) is a subgroup of \(C_p\).
    • The Fundamental Lemma of Homology states \(\partial_p \partial_{p+1} d = 0\), which implies that every boundary is a cycle, so \(B_p \subseteq Z_p\).
  • Homology Group (\(H_p\)): The \(p\)-th homology group is the quotient group \(H_p(K) = Z_p(K) / B_p(K)\). Its elements are homology classes.
  • Betti Number (\(\beta_p\)): The rank of the \(p\)-th homology group, \(\beta_p = \text{rank } H_p(K)\). For \(\mathbb{Z}_2\) coefficients, \(\beta_p = \text{rank } Z_p - \text{rank } B_p\). \(\beta_p\) counts the number of \(p\)-dimensional holes.

Homology (Chapter IV)

Exact Sequences

  • A sequence of vector spaces (or groups) and homomorphisms \(\dots \xrightarrow{f_{i-1}} V_i \xrightarrow{f_i} V_{i+1} \xrightarrow{f_{i+1}} \dots\) is exact at \(V_{i+1}\) if \(\text{im } f_i = \ker f_{i+1}\).
  • Long exact sequences are powerful tools for relating different homology groups.
  • Mayer-Vietoris Sequence: A specific long exact sequence that relates the homology groups of a space \(K = K' \cup K''\) to the homology groups of \(K'\), \(K''\), and their intersection \(A = K' \cap K''\).
    • \(\dots \to H_p(A) \to H_p(K') \oplus H_p(K'') \to H_p(K) \to H_{p-1}(A) \to \dots\).
    • Provides a divide-and-conquer approach to computing homology.

Morse Functions (Chapter VI)

Real-valued functions used to analyze the topology of manifolds.

Generic Smooth Functions

  • Smooth functions are preferred over general continuous functions for analysis.
  • Critical Point: A point \(x \in M\) where the derivative (gradient) \(Df_x\) of \(f: M \to \mathbb{R}\) is the zero map. In local coordinates, all partial derivatives vanish.
  • Non-degenerate Critical Point: A critical point \(x\) where the Hessian matrix \(H(x)\) (matrix of second partial derivatives) is non-singular (det \(H(x) \ne 0\)).
    • The index of a non-degenerate critical point is the number of minus signs in the quadratic polynomial representation given by the Morse Lemma (or number of negative eigenvalues of its Hessian).
  • Morse Function: A smooth function \(f: M \to \mathbb{R}\) such that (i) all its critical points are non-degenerate, and (ii) all critical points have distinct function values.

Handle Decomposition & Morse Complex

  • Attaching Handles: When increasing the threshold of a Morse function \(f\), the homotopy type of the sublevel set \(M_a = f^{-1}(-\infty, a]\) changes only when \(a\) passes a critical value. This change is homotopically equivalent to attaching a \(q\)-handle, where \(q\) is the index of the critical point.
  • Morse-Smale Function: A Morse function whose stable and unstable manifolds intersect transversally.
  • Morse-Smale Complex: For a Morse-Smale function, its vertices are the critical points of \(f\). Cells are components of intersections of stable and unstable manifolds. Edges, for instance, are isolated integral lines connecting critical points whose indices differ by one. This complex can be used to compute Floer homology.

Morse Functions (Chapter VI)

Piecewise Linear (PL) Functions

  • Analogous concepts for functions on triangulated manifolds where the function is linear on each simplex.
  • Lower Star / Lower Link:
    • Lower Star (St⁻\(u_i\)): For a vertex \(u_i\) in a PL function \(f\) (where vertices are ordered by function value), St⁻\(u_i\) consists of all simplices \(\sigma\) in St \(u_i\) for which \(u_i\) is the vertex with the maximum function value.
    • Lower Link (Lk⁻\(u_i\)): Simplices in Lk \(u_i\) whose vertices all have function values less than \(f(u_i)\).
  • PL Critical Vertex: A vertex \(u_i\) is a simple PL critical vertex of index \(q\) if its lower link Lk⁻\(u_i\) has the reduced homology of a \((q-1)\)-sphere (i.e., \(\widetilde{\beta}_{q-1}(\text{Lk}^-u_i)=1\) and other reduced Betti numbers are 0).
  • PL Morse Function: A PL function where each vertex is either PL regular (lower link homologically trivial) or simple PL critical, and all vertices have distinct function values.

Reeb Graphs

  • Visualizes the evolution of the connected components of level sets of a function \(f: X \to \mathbb{R}\).
  • The Reeb graph \(R(f)\) is the quotient space where points in \(X\) are equivalent if they belong to the same connected component of the same level set.
  • Nodes in the Reeb graph typically correspond to critical points of \(f\) where the topology of the level set components changes (merge or split).
  • If \(X\) is contractible (e.g., a cube in medical imaging), \(R(f)\) is a tree (called a contour tree).
  • Can be constructed by sweeping through function values and tracking changes in level set components.

Persistence (Chapter VII)

Measures the scale or resolution of topological features within data, particularly useful for handling noise.

Persistent Homology

  • Filtration: A nested sequence of simplicial complexes \(\emptyset = K_0 \subseteq K_1 \subseteq \dots \subseteq K_n = K\). This sequence is often derived from a monotonic function \(f: K \to \mathbb{R}\) where \(K_i = K(a_i) = f^{-1}(-\infty, a_i]\) for sorted values \(a_i\).
  • Birth and Death: As one moves through the filtration:
    • A homology class \(\gamma \in H_p(K_i)\) is born at \(K_i\) if it is not in the image of the map from \(H_p(K_{i-1})\) (i.e., \(\gamma \notin H_p^{i-1,i}\)).
    • It dies entering \(K_j\) if it merges with an older class (born at \(K_{k}\) with \(k < i\)) when going from \(K_{j-1}\) to \(K_j\).
    • The Elder Rule governs this: at a merge, the “older” class (born earlier) persists, and the “younger” one dies.
  • Persistence: For a class born at \(K_i\) (value \(a_i\)) and dying at \(K_j\) (value \(a_j\)), its persistence is \(a_j - a_i\).
  • Persistent Betti Number (\(\beta_{i,j}^p\)): The rank of \(H_p^{i,j} = \text{im}(f_p^{i,j}: H_p(K_i) \to H_p(K_j))\). It counts \(p\)-dimensional classes born at or before \(K_i\) that are still alive at \(K_j\).
  • Persistence Diagram (Dgm\(_p(f)\)): A multiset of points \((a_i, a_j)\) in \(\overline{\mathbb{R}}^2\), where \(a_i\) is the birth value and \(a_j\) is the death value of a \(p\)-dimensional homology class. Points are above the diagonal \(y=x\); diagonal points (often added with infinite multiplicity) represent features with zero persistence. The vertical distance to the diagonal is the persistence.

Persistence (Chapter VII)

Implementation

  • Persistent homology can be computed efficiently using matrix reduction on a single boundary matrix \(\partial\) whose rows and columns are ordered compatibly with the filtration.
  • The algorithm performs left-to-right column additions to obtain a reduced matrix \(R = \partial V\).
  • The lowest one in a column \(j\) of \(R\), say at row \(i\) (i.e., \(i=\text{low}(j)\)), indicates that simplex \(\sigma_i\) (birth) is paired with simplex \(\sigma_j\) (death).
    • If column \(j\) is zero, \(\sigma_j\) gives birth to a class that might persist indefinitely (or until paired later in an extended context).
  • This algorithm computes all pairs \((birth, death)\) for the persistence diagram.
  • Sparse matrix implementations are more efficient for large datasets, improving upon the general cubic worst-case complexity. For the 0th persistence diagram, it can be computed in nearly linear time using a union-find data structure.

Spectral Sequences

  • A theoretical tool in algebraic topology that provides a way to compute homology groups of a filtered space in stages.
  • The algorithm involves reducing the boundary matrix in phases, sweeping diagonally.
  • The groups \(E^r_{p,q}\) in the spectral sequence represent homology classes that persist for at least \(r\) “steps” in the filtration (related to the index difference in the function values).
  • The Spectral Sequence Theorem states that the total rank of \(E^r_{p,q}\) (for fixed dimension \(p+q\)) equals the number of points in the \((p+q)\)-th persistence diagram with persistence \(\ge r\).

Stability (Chapter VIII)

Concerns how persistence diagrams (and thus the measured features) change when the input function or data undergoes small perturbations.

Stability Theorems

  • Bottleneck Distance (\(W_\infty(X, Y)\)): A metric between two persistence diagrams \(X\) and \(Y\). It’s the infimum, over all bijections \(\eta: X \to Y\) (matching points in \(X\) to points in \(Y\), including points on the diagonal), of the supremum \(L_\infty\)-distance between matched points: \(W_\infty(X, Y) = \inf_{\eta} \sup_{x \in X} \|x - \eta(x)\|_\infty\).
  • Stability Theorem for Filtrations (and Tame Functions): A fundamental result stating that the bottleneck distance between the \(p\)-th persistence diagrams of two monotonic functions \(f, g\) on a simplicial complex \(K\) (or two tame functions on a triangulable space \(X\)) is bounded by the \(L_\infty\)-distance between the functions:
    • \(W_\infty(\text{Dgm}_p(f), \text{Dgm}_p(g)) \le \|f - g\|_\infty\).
    • This means small changes in the function lead to small changes in the persistence diagram (when distance is measured by \(W_\infty\)).
  • Vines and Vineyards: When considering a straight-line homotopy \(f_t = (1-t)f + tg\) between two functions, the points in the persistence diagrams Dgm\(_p(f_t)\) trace out polygonal paths called “vines”. The collection of these paths is a “vineyard”. The existence of these connected vines is a manifestation of stability.

Packages

tdaverse

  • ripserr
  • inphr
  • tdarec
  • phutil
  • tdarec-grant

tdaverse

  • ggtda
  • tdaverse
  • tdaunif
  • interplex

Other R Packages

  • BayesTDA
  • simplextree
  • TDAstats